package leetcode每日一题;

/**
 * 1. 问题描述
 *      数组的每个索引作为一个阶梯，第i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。
 *      每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
 *      您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
 *
 * 2. 算法分析
 *      动态规划很容易想到，对于此题我们有一个针对于动态规划的题目的一个优化：使用滚动数组
 *      此时我们不需要开辟额外的空间创建动态数组，只需要设置两个指针即可，空间复杂度可以优
 *      化为O(1)
 *
 *      什么是滚动数组?
 *          滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，
 *          来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中（如01背包问题）。
 *          因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。
 *          所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
 *
 *      如何使用滚动数组优化动态规划的题目?
 *          首先我们知道对于一般的动态规划的题目，我们主要是求解一个所谓的动态方程：
 *              dp[i]的状态由dp[i-1]和dp[i-2]的状态表示，类似于一个递推式
 *          此时我们发现dp[i]只与dp[i-1]和dp[i-2]有关，由此我们考虑使用两个人移
 *          动指针来记录当前第个i个状态的第i-1和i-2的状态，每轮更新，这样我们就节省
 *          了一个dp数组的空间，从而达到优化
 *
 *          其次
 *
 *      具体的题目案例
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 使用最小花费爬楼梯 {
    public static void main(String[] args) {

    }

    // 从右到左dp
    public static int minCostClimbingStairs1(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        //从倒数第一个阶梯到顶部只有一种选择
        dp[len-1] = cost[len-1];
        //从倒数第二个阶梯到顶部只有两种选择，但是我们一次可以爬两个阶梯，所以最小体力肯定是直接从倒数第二个阶梯到顶部
        dp[len-2] = cost[len-2];
        for(int i = len-3; i >= 0; i--) {
            // 从第i个阶梯到顶部的两种方式
            // 从第i到i+1，在从第i+1到顶部
            // 从第i到i+2，在从第i+2到顶部
            // 取两种情况中最小的
            dp[i] = Math.min(cost[i]+dp[i+1],cost[i]+dp[i+2]);
        }
        return Math.min(dp[0],dp[1]);
    }

    // 从左到右dp
    public int minCostClimbingStairs2(int[] cost) {
        int len = cost.length;
        //  为什么dp数组的长度为len+1 ，因为如果将顶部算上就是len+1个阶梯
        //  如果设置为len，当我们在计算最后一个台阶的时候就已经结束了，但是此时我们还没有到达
        // 顶部，需要从花费最后一个阶梯的体力或者倒数第2个阶梯的体力，所以此时我们就没有计算完全
        int[] dp = new int[len+1]; // dp[i]表示到第i个台阶需要花费的最小体力
        dp[0] = dp[1] = 0; // 因为可以从第1个台阶或者第2个台阶开始对应的索引为0或者1
        for(int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[len];
    }

    //  滚动数组  此时不需要额外的dp数组空间，空间复杂度为O(1)
    public int minCostClimbingStairs3(int[] cost) {
        /**
         * 对应上述的dp数组的形式改写即可，注意更新的顺序
         */
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}
